\documentclass[a4paper,10pt,reqno]{amsart}

\usepackage{amsfonts, amsmath, amsthm, amssymb}
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage{lmodern}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{a4wide}
\usepackage{microtype}
\pagestyle{plain}
\usepackage[colorlinks=true,linkcolor=black]{hyperref}
\usepackage[lofdepth,lotdepth]{subfig}
\usepackage{moreverb}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing}

\hypersetup{pdftitle={EU-Rent, Matus Tejiscak, 4176200}}

\newcommand{\true}{\mathsf{true}}
\newcommand{\false}{\mathsf{false}}

\newcommand{\mint}[1]{\mathrm{#1}}
\newcommand{\then}{\Rightarrow}
\newcommand{\tpl}[2]{\textsf{#1(#2)}:}

%\frenchspacing

\title{EU-Rent}
\author{Matúš Tejiščák \\ 4176200}
\date{\today}

\begin{document}

\maketitle

\section{The domain and expert model}

\subsection{Overview}

For this assignment, I chose to model customer evaluation based on a sequence of \emph{events},
as recorded in the history of the company.

As the company does its business renting cars, \emph{events} naturally occur. An event is, for
example,
\begin{itemize}
	\item reservation of a car;
	\item actual rental of a car (either reserved or walk-in);
	\item drop-off (returning) of a car;
	\item a question about eligibility of a customer to rent a car.
\end{itemize}
Given a sequence of events, the system should
\begin{itemize}
	\item answer all questions contained in the sequence;
	\item point out some interesting facts derivable from the history (for example that
		a drop-off is in fact a day later than agreed on in the rental agreement and the
		customer needs to be charged additional fees).
\end{itemize}
No branches are considered and most of the rules in the assignment have been neglected. Instead,
I chose to implement a small self-contained (though hopefully non-trivial) portion of the rules.

\subsection{Events and history}

History is a sequence of events. An event, as described above, is a~\emph{reservation},
\emph{rental}, \emph{drop-off}, or \emph{can-rent} (a question about eligibility). All events
are tagged by the date they occur on and they are sorted in a linear order.

\subsection{Trouble}
\label{subsection:trouble}

Every customer accumulates trouble points. Once the customer reaches the threshold value, they are
put on the blacklist. (In this model, no time-decay/discount is considered so the trouble score
cannot decrease.)

Trouble points are completely separate from possible additional fees caused by the problem on
customer's part; they are there to filter out problematic customers and have no financial meaning.

The penalty is
\begin{itemize}
	\item 5 points per day for returning a car too early;
	\item 20 points per day for returning a car too late;
	\item 30 points for not showing up despite having a reservation;
	\item 50 points for returning a car in a bad condition;
	\item \ldots adding up to a 100-point threshold that, once reached, puts the customer
		on the blacklist.
\end{itemize}

\subsection{Customers}

Dealing with customers is very simple in this model. Each customer is identified by their name,
can be assigned a certain amount of trouble and can be put on a blacklist. No additional information
is represented (no credit card info, no address etc.) since it either does not play role or is
implicit.

\subsection{Requested information}

We are especially interested in
\begin{itemize}
	\item answering questions in the history
	\item marking late and early drop-offs as such;
	\item recognizing abandoned reservations (no credit-card distinctions are made, in contrast with
		the rules in the assignment, we just expect every customer to back up their reservation with
		a credit card);
	\item listing customers blacklisted in the process;
	\item (possibly) listing all trouble records.
\end{itemize}

\subsection{Rules}

\subsubsection{Eligibility to rent a car}

\begin{itemize}
	\item A blacklisted person cannot rent a car.
	\item A customer cannot rent a car if they already have one.
\end{itemize}

\subsubsection{Trouble}

Trouble points are given for
\begin{itemize}
	\item not showing up in spite of a reservation;
	\item returning the car in a bad condition;
	\item returning the car too early;
	\item returning the car too late;
\end{itemize}
as described above in Section \ref{subsection:trouble}.
If the customer reaches the threshold of 100 trouble points, they are automatically put on the
blacklist.


\section{An example application}

\noindent The obvious application is in a setting of a small car-renting company. The task is twofold:
\begin{itemize}
	\item When a customer wants to make a reservation, we need to be able to tell whether
		we are willing to trust them.
	\item At the end of each day, we want to know which customers we need to charge extra fees
		for that day because they returned cars too late or too early, which customers we want
		to charge for not showing up despite a reservation (so we can cancel the reservation),
		and, finally, which customers have gotten to the blacklist during that day.
\end{itemize}

\section{The program}

\subsection{Templates}

Let us start by introducing the hierarchy of entities (templates) used in the \textsc{Jess} program.
We will denote optional slots (having default values) with \textsf{[square brackets]} and
auto-inferred slots (that are not to be filled in in the history) with \textsf{\{curly brackets\}}.

\begin{itemize}
	\item \tpl{event}{seq, date} A general \emph{event}, occurring at a specific position
		in the history, denoted by \textsf{seq}, which is in fact the ordinal number of the event
		within the sequence. Also carries a~\textsf{date} when the event occurred.
	\begin{itemize}
		\item \tpl{request}{customer-name, from-date, days}
			A general request for reservation from a~specific \textsf{date}, for the given number
			of \textsf{days}.
			\begin{itemize}
				\item \tpl{can-rent?}{\{answer, reason\}} A question about eligibility of the
					person to rent a~car. All explicit fields are inherited from \textsf{request};
					these serve for the underlying machinery.
					
					An important point about this event is that the answer to that question
					will be relevant \emph{at the time of asking}. For example, if a person
					is later blacklisted, they can still receive a positive answer at an earlier
					date.
				\item \tpl{reservation}{} An accepted reservation. Again, all explicit fields
					are inherited from the ancestors.
			\end{itemize}
		\item \tpl{rental}{customer-name, \{dropoff-event-seq, until\}}
			A general rental, specified further in the descendant templates.
			\begin{itemize}
				\item \tpl{reserved-rental}{reservation-seq} A simple pick-up of a pre-reserved
					car.
				\item \tpl{walkin-rental}{days} A walk-in rental, starting immediately
					(on the day given by the slot \textsf{date} inherited from \textsf{event}),
					with duration of several \textsf{days}.
			\end{itemize}
		\item \tpl{drop-off}{customer-name, [condition], \{rental-seq, days-late, condition\}}
			A drop-off event that occurs when a \textsf{customer} returns a rented car. That
			car can be in \textsf{good} or \textsf{bad} \textsf{condition}.
		\item \tpl{blacklist}{customer-name, reason} A blacklist event when a
			\textsf{customer-name} is deemed blacklisted for some \textsf{reason}.
	\end{itemize}
	
	\item \tpl{trouble}{\{seq, customer-name, score, total-score, previous-trouble\}} A trouble
		caused by the event nr. \textsf{seq}, with individual "badness" \textsf{score},
		total badness (including self) equal to \textsf{total-score} and a seq number of the
		\textsf{previous-trouble}.
\end{itemize}

\subsection{Data types and representation}

Most data types are obvious; we use Boolean variables for truth values, integral variables for
numeric values, strings for names. Most variables are also nullable, taking the special value
\textsf{nil} to denote they are undefined.

The most notable is probably the date type. Date is represented by natural numbers, as the
count of days from an arbitrary starting point. This is done to make the date arithmetic feasible
and, in practice, it would be easily convertible by a specialized program anyway.

\subsection{Rules}

The complete set of rules is -- of course -- written in full in the source code. Here I'm going
to list just the main ideas behind the implementation.

\subsubsection{Eligibility}
\label{section:eligibility}

This is implemented in two rules, \textsf{can-rent-blacklist} and \textsf{can-rent-multiple}.
If a person was blacklisted at some point before asking the question, the answer to that question
must be negative. As for multiple rentals, if there is a rental in the past but no drop-off
between that point and the question, the answer will be negative because the car has not been
returned yet.

Later, when answers are printed out, a positive answer or a \textsf{nil} answer are both interpreted
as positive since unless there is a reason not to let the customer hire a car, we want to allow
them to do so.

\subsubsection{Rentals}

First, there are rules to calculate the \textsf{until} slot, which is necessary to have uniform
access to all rentals, regardless of whether they are walk-in or reserved.

Then there are rental-dropoff pairing rules. The rule \textsf{dropoff-binder-handler} connects
the corresponding rentals and drop-offs, calculating how many \textsf{days-late} the drop-off
is. This is done just by pairing the nearest rentals and drop-offs that have no other rentals
and drop-offs between them.

Finally, there is the \textsf{dropoff-missing} rule that looks for rentals without a matching
drop-off. Such rentals will get \textsf{dropoff-event-seq} equal to 0.

\subsubsection{Trouble}

Trouble is implemented as side items, "tags" attached to events.

If a customer fails to show up
despite having reserved a car on a particular day, a trouble tag is attached to that reservation
event by the rule \textsf{trouble-noshow}, which implies a penalty of several trouble points to the
customer.

Also, when a customer returns a car in a not-so-good condition, returns it too late or too early,
a trouble tag is created with an appropriate score by the rule \textsf{trouble-dropoff}.

Then there is the trouble-counting machinery. Every trouble item is assigned its immediate
predecessor (considering troubles of a single customer only). If there is no predecessor, the rule
\textsf{trouble-init} initializes the \textsf{total-score} slot of that trouble item to an
appropriate non-\textsf{nil} value, which causes a cascade of updates done by
\textsf{trouble-accumulation}. This rule searches for immediate predecessors and calculates
cumulative sums of trouble scores.

\subsubsection{Blacklisting}

Once cumulative trouble (for a customer) reaches a certain level, the rule \textsf{trouble-blacklist}
fires and attaches a blacklist "tag" to the event that caused the trouble overflow. All subsequent
queries for eligibility will end up negative.

There's also one technical rule called \textsf{blacklist-prune} that retracts all redundant
blacklist tags (i.e. those that already are preceded by another blacklist tag). This is to
keep \textsf{trouble-blacklist} simple.

\subsubsection{Dumping}
\label{section:dumping}

The inference machine is non-deterministic. However, we would like to have the output sorted
by the sequence number; in other words, we want the answers in the same order as the questions
we asked.

This is achieved by not printing anything at all during the inference period. All answers are
kept as facts and after the inference period, a special fact \textsf{dump-answers} is asserted
and the inference machinery is rerun.

The fact \textsf{dump-answers} actually takes one parameter called \textsf{seq} that determines
what event gets printed its answers in that iteration. The whole thing is then directed by
a recursive function called \textsf{dump} that reruns the machine for different values of
\textsf{seq}, starting from one, incrementing by one in each iteration.

Hence the program contains rules specialized to data dumping during this "second pass". All these
rules are constrained by the assumption \texttt{(dump-answers (seq ?seq))} so that they fire exactly
when they have to.

There are rules \textsf{dump-positive} and \textsf{dump-negative} to print information about
positive and negative answers to questions asked in the event sequence. (I remind that,
as mentioned in Section \ref{section:eligibility}, a \textsf{nil} value is considered positive here
since it means that there are no reasons to reject the customer).

There are also rules \textsf{dump-early-dropoffs} and \textsf{dump-late-dropoffs} that rely
on information calculated by the main inference loop, especially the \textsf{days-late} slot
of drop-off events.

The other rules include \textsf{dump-blacklists}, that prints information about customers being
blacklisted at that point, \textsf{dump-noshow}, that prints notices about no-show reservations
and (optional) \textsf{dump-trouble}, that prints information about trouble tags attached to events.

\subsection{Top-level machinery}

Most of this has been described in Section \ref{section:dumping} about dumping.

First, the program starts inference with the standard rules and facts from the history. This
calculates everything we want to infer from the body of knowledge specified as the history sequence.
Next, the recursive function \textsf{dump} is called that
reruns inference for different arguments of the fact \textsf{dump-answers}, which causes
the discovered answers to be printed in the required order.

\section{An example consultation}

\noindent An example input is shown in Figure \ref{listing:history} on page
\pageref{listing:history}. The corresponding output is shown in the next Figure \ref{listing:output}
on page \pageref{listing:output}. In this single example, we can observe several features of the
system.
\begin{itemize}
	\item First, we blacklist Evil Joe and subsequently we check whether he can rent a car.
		Of course, the answer is negative, given together with the correct reason.
	\item Next, we run a similar query for Mary Lou, who is a completely new client. In her case,
		the answer is positive.
	\item If we let Mary Lou reserve and rent a car, she cannot rent more cars until she returns
		the current one.
	\item If we make Mary return the car one day too late, the system notices and prints
		a correct warning.
	\item Conversely, if John Qik returns the car 2 weeks too early, the system prints a correct
		warning. Also, in the background, it keeps the increased trouble score for John.
	\item Next we make Mary Lou return two cars late, the first one even in a bad condition.
		The trouble counter obviously overflows after the second drop-off and Mary Lou
		gets blacklisted. The subsequent request for rental is rejected.
	\item Finally, we make John Qik reserve a car but never pick it up. The result is
		John ending up on the blacklist and being refused rentals.
\end{itemize}

\begin{figure}[htp]
\centering\small
\begin{listing}{1}
(deffacts records
  (blacklist
    (seq  1) (date  1) (customer-name "Evil Joe") (reason "known bad boy"))
  (can-rent?
    (seq  2) (date  2) (customer-name "Evil Joe") (from-date 2) (days 5))
  (can-rent?
    (seq  3) (date  2) (customer-name "Mary Lou") (from-date 4) (days 5))
  (reservation
    (seq  4) (date  2) (customer-name "Mary Lou") (from-date 3) (days 5))
  (reserved-rental
    (seq  5) (date  3) (customer-name "Mary Lou") (reservation-seq 4))
  (walkin-rental
    (seq  6) (date  4) (customer-name "John Qik") (days 20))
  (can-rent?
    (seq  7) (date  4) (customer-name "Mary Lou") (from-date 4) (days 5))
  (drop-off
    (seq  8) (date  9) (customer-name "Mary Lou"))
  (drop-off
    (seq  9) (date 10) (customer-name "John Qik"))
  (walkin-rental
    (seq 10) (date 10) (customer-name "Mary Lou") (days 1))
  (drop-off
    (seq 11) (date 12) (customer-name "Mary Lou") (condition bad))
  (walkin-rental
    (seq 12) (date 13) (customer-name "Mary Lou") (days 1))
  (drop-off
    (seq 13) (date 15) (customer-name "Mary Lou"))
  (can-rent?
    (seq 14) (date 16) (customer-name "Mary Lou") (from-date 16) (days 5))
  (reservation
    (seq 15) (date 17) (customer-name "John Qik") (from-date 17) (days 5))
  (can-rent?
    (seq 16) (date 17) (customer-name "John Qik"))
)
\end{listing}
\normalsize
\caption{An example history given to the system as an input}
\label{listing:history}
\end{figure}

\begin{figure}[htp]
\vspace{1cm}
\centering\small
\begin{listing}{1}
1: Evil Joe has been blacklisted: known bad boy
2: Evil Joe can NOT rent a car: blacklisted
3: Mary Lou can safely rent a car.
7: Mary Lou can NOT rent a car: previous car not returned yet
8: This is a late drop-off. Charge Mary Lou for 1 extra day(s).
9: John Qik returned the car 14 days too early.
11: This is a late drop-off. Charge Mary Lou for 1 extra day(s).
13: Mary Lou has been blacklisted: too much trouble
13: This is a late drop-off. Charge Mary Lou for 1 extra day(s).
14: Mary Lou can NOT rent a car: blacklisted
15: John Qik did not show up for the reservation. Charge him.
15: John Qik has been blacklisted: too much trouble
16: John Qik can NOT rent a car: blacklisted
\end{listing}
\normalsize
\caption{The corresponding output of the system}
\label{listing:output}
\end{figure}

\section{Conclusions}

\noindent The system is useful for automating the most common tasks when evaluating customers.
Using just historical records of events, it can automatically infer which customers are trustworthy
and which are not. As a side effect, it also prints some auxiliary facts that are useful
in accounting (who to charge and how much).

Of course, the program has its shortcomings. Most importantly, it's very simple and covers
just a small set of rules. There are also little semantic quirks: for example, if we look at the
listing in the Figure \ref{listing:history}, we may expect the very last query to give
the positive answer because John Qik presumably hasn't had a chance to return the car on day 17 and
it's therefore unfair to deem him not trustworthy just because our data is incomplete.

I decided to stop at this level of complexity, which makes for a rather self-contained business
model, which is easy to understand and experiment with.

\end{document}




























